public class Sort {

    /*
    直接排序:
        时间复杂度:
            最好情况:(数据全部有序)-->O(n)
            最坏情况:(顺序全部相反)-->O(n^2)
        空间复杂度:O(1)
        稳定性:稳定的
            一个本身就不稳定的排序,是不可能变成一个稳定的排序的
            但是一个本身就稳定的排序是可以实现为不稳定的排序
     */
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >=0 ; j--) {
                if(array[j]>tmp){//-->加不加等号,取决于稳定性-->加上等号是稳定的
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }


    /*
    希尔排序:
        时间复杂度:不固定
        空间复杂度:
        稳定度:不稳定
     */
    public static void ShellSort(int[] array){
        int gap = array.length;
        while(gap>1){
            gap = gap/3+1;
            shell(array,gap);
        }

    }

    private static void shell(int[] array,int gap){
        //其中用插入排序
        for (int i = gap; i <array.length ; i++) {
            int tmp = array[i];
            int j = i-gap;
            for(;j>=0;j--){
                if(array[j]>tmp){
                    array[j+gap] = array[j];
                }else{
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }



    //选择排序
    public static void selectSort(int[] array){
        int tmp = 0;
        for(int i = 0;i<array.length;i++){
            tmp = array[i];//这是选的最小的
            int j=i+1;
            for(;j<array.length;j++){
                if(array[j]<tmp){
                    tmp = array[j];//找到了最小
                    array[j] = array[i];
                    array[i]=tmp;
                }
            }
        }
    }

    //选择排序2 用左右一起遍历

    //自写
    public static void selectSort2(int[] array){
        //有一个最大值和最小值的下标
        int max,min;
        int right = array.length-1; //右边下标
        int left = 0;//左边下标
        while (left<right){
            int i=left+1;
            min = left;
            max = right;
            for(;i<=right;i++){
                if(array[i]>array[max]){
                    max = i;
                }
                if(array[i]<array[min]){
                    min=i;
                }
            }
            int tmp = array[left];
            array[left] = array[min];
            array[min]=tmp;
            tmp=array[right];
            array[right] = array[max];
            array[max] = tmp;
            left++;
            right--;
        }
    }

    //课程代码
    public static void selectSort3(int[] array){
        int left = 0;
        int right = array.length-1;
        while(left<right){
            int minIndex = left;
            int maxIndex = left;
            for (int i = left+1; i <=right ; i++) {
                if(array[i]<array[minIndex]){
                    minIndex = i;
                }
                if(array[i]>array[maxIndex]){
                    maxIndex = i;
                }
            }
            swap(array,minIndex,left);
            swap(array,maxIndex,right);
            left++;
            right--;
        }
    }

    public static void swap(int[] array,int index1, int index2){
        int tmp=array[index1];
        array[index1]=array[index2];
        array[index2]=tmp;
    }


    //堆排序
    public static void heapSort(int[] array){
        //创建大根堆
        createHeap(array);
    }

    public static void createHeap(int[] array){
        int parent=(array.length-1-1)/2;
        for (;parent>=0;parent--){
            sitfDown(array,parent,array.length);
        }
    }

    public static void sitfDown(int[] array,int parent,int len){
        int child = (parent*2)+1;
        while(child<len){
            //证明有子节点``
            if(child+1<len&&array[child]<array[child+1]){
                //证明有右子节点
                child=child+1;
            }
            if(array[child]>array[parent]){
                //此时说明没有成为大根堆
                swap(array,child,parent);
                parent = child;
                child = parent*2+1;
            }else{
                break;
            }
        }
    }

    public static void bubbleSort(int[] array){
        //i代表趟数
        for (int i = 0; i < array.length-1; i++) {
            boolean flag = false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flag=true;
                }
            }
            //没有交换则本身有序
            if(flag==false){
                return;
            }
        }
    }

    public static void quickSort(int[] array){
        quick(array,0, array.length-1);
    }

    private static void quick(int[] array,int start,int end){
        if(start>=end){
            return;
        }
        int pivot = partition(array,start,end);//相遇的位置

        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    private static int partition(int[] array,int left,int right){
        int tmp = array[left];//基准
        int i = left;
        while(left<right) {
            while (left < right && array[right] >= tmp) {
                //防止越界
                right--;
            }

            while (left < right && array[left] <= tmp) {
                left++;
            }
            swap(array, left, right);
        }
        swap(array,i,left);
        return left;
    }



    //非递归实现归并排序
    public static void mergeSortNor(int[] array){
        int gap = 1;//空隙

        while(gap< array.length){

            for(int i=0;i<array.length;i=i+2*gap){
                int left=i;
                int mid = left+gap-1;
                if(mid>=array.length){
                    mid= array.length-1;
                }
                int right = mid+gap;
                if(right>= array.length){
                    right = array.length-1;
                }

                //这里使用递归归并排序
            }

            gap*=2;
        }
    }




    public static void countSort(int[] array){
        //1.求最值
        int max = array[0];
        int min = array[0];
        for (int i = 0; i <array.length ; i++) {
            if(max<array[i]){
                max = array[i];
            }
            if(min>array[i]){
                min=array[i];
            }
        }

        //2.定义计数数组 初始化
        int[] count = new int[max-min+1];
        int k=0;//array数组下标
        for (int i = 0; i <array.length ; i++) {
            int index = array[i]-min;
            count[index]++;
        }

        //3.遍历计数数组
        for (int i = 0; i <count.length ; i++) {
           while (count[i]!=0){
               array[k] = count[i]+min;
               k++;
               count[i]--;
           }
        }
    }
}
